package com.cuz.daileetcode.暴力递归记忆化搜索动态规划;

import java.util.Arrays;

/**
 * @author cuzz
 * @version 1.0
 * @description: 见【暴力递归->记忆化搜索->动态规划1】
 * @date 5:38 2022/1/6
 **/
public class RobotMovement {
    public static void main(String[] args) {
        System.out.println(moveWayCount(5, 2, 4, 4));
    }

    /**
     * @param N 1~N可以停留
     * @param S 机器人起始位置
     * @param E 机器人目标位置
     * @param K 总步数
     * @return int 总共的走法
     */
    public static int moveWayCount(int N, int S, int E, int K) {
//        return Recursion.recursion(N, S, E, K);
//        int[][] memory = new int[N + 1][K + 1];
//        for (int row = 0; row < memory.length; row++) {
//            Arrays.fill(memory[row], -1);
//        }
//        return MemorySearch.recursion(N, S, E, K, memory);
        return DynamicProgramming.dynamicProgramming(N, S, E, K);
    }

    /****
     * 递归怎么做
     */
    static class Recursion {
        /**
         * @param N         1~N可以停留
         * @param curIndex  机器人当前位置
         * @param E         机器人目标位置
         * @param resetStep 剩余步数
         * @return int 总共的走法
         */
        static int recursion(int N, int curIndex, int E, int resetStep) {
            if (resetStep == 0) {
                if (curIndex == E) {
                    return 1;
                } else {
                    return 0;
                }
            }
            if (curIndex == 1) {
                return recursion(N, 2, E, resetStep - 1);
            }
            if (curIndex == N) {
                return recursion(N, N - 1, E, resetStep - 1);
            }
            return recursion(N, curIndex + 1, E, resetStep - 1)
                    + recursion(N, curIndex - 1, E, resetStep - 1);
        }
    }

    /****
     * 记忆化搜索
     */
    static class MemorySearch {
        /**
         * @param N         1~N可以停留
         * @param curIndex  机器人当前位置
         * @param E         机器人目标位置
         * @param resetStep 剩余步数
         * @param memory    优化递归的记忆数组
         * @return int 总共的走法
         */
        static int recursion(int N, int curIndex, int E, int resetStep, int[][] memory) {
            int res;
            if (resetStep == 0) {
                if (curIndex == E) {
                    return 1;
                } else {
                    return 0;
                }
            }
            //如果没有命中缓存
            if (memory[curIndex][resetStep] == -1) {
                //求值
                if (curIndex == 1) {
                    res = recursion(N, 2, E, resetStep - 1, memory);
                } else if (curIndex == N) {
                    res = recursion(N, N - 1, E, resetStep - 1, memory);
                } else {
                    res = recursion(N, curIndex + 1, E, resetStep - 1, memory)
                            + recursion(N, curIndex - 1, E, resetStep - 1, memory);
                }
                //写缓存
                memory[curIndex][resetStep] = res;
            } else {
                //命中缓存 返回缓存内容即可
                res = memory[curIndex][resetStep];
            }
            return res;
        }
    }

    static class DynamicProgramming {
        /**
         * @param N 1~N可以停留
         * @param S 机器人起始位置
         * @param E 机器人目标位置
         * @param K 总步数
         * @return int 总共的走法
         */
        static int dynamicProgramming(int N, int S, int E, int K) {
            int[][] dp = new int[K + 1][N + 1];
            dp[0][E] = 1;
            for (int restStep = 1; restStep <= K; restStep++) {
                for (int cur = 1; cur <= N; cur++) {
                    if (cur == 1) {
                        dp[restStep][cur] = dp[restStep - 1][2];
                        continue;
                    } else if (cur == N) {
                        dp[restStep][cur] = dp[restStep - 1][N - 1];
                        continue;
                    }
                    dp[restStep][cur] = dp[restStep - 1][cur + 1] + dp[restStep - 1][cur - 1];
                }
            }
            return dp[K][S];
        }
    }
}
